In a multiple processor computing apparatus, such as a supercomputer, the processors are typically interconnected by a network of interconnected routers, at least some of which are connected to the respective processors. Each of the routers is also connected to a plurality of other routers in the network. In such a computing apparatus, it is of course important to route communications among the processors in an efficient manner. Perhaps more importantly, however, is the need to avoid deadlock situations in the network of routers. A deadlock situation can exist, for example, when each of a plurality of routers that are interconnected with one another to form a ring or loop has a message for the next adjacent router in the loop, and all of these messages are traveling in the same direction around the loop. This type of deadlock condition, and many others, are well documented in the art.
Another important aspect of routing is fault tolerance. The system should preferably be able to avoid deadlock, even when one or more of the routers becomes inoperative (fails).
Another important aspect of operating a multiple processor computing apparatus is the allocation of processors to execute applications. For any given job, the efficiency with which that job can be performed or executed is impacted by the set of P processors allocated to perform that job. For example, if first and second different sets of P processors can be allocated to perform the job, one of the sets of P processors will typically perform the job less efficiently than would the other set of P processors.
It is desirable in view of the foregoing to provide for fault tolerant, deadlock-free routing, and efficient processor allocation in a multiple processor computing apparatus.
Exemplary embodiments of the invention utilize directional routing restrictions and a virtual (logical) channel construct to provide fault tolerant, deadlock-free routing in a multiple processor computing apparatus. Some exemplary embodiments perform processor allocation by creating a linear ordering of the processors based on routing rules used for routing communications between the processors. In some embodiments, the linear ordering of processors loops back around upon itself, and bin-packing algorithms are applied to this linear ordering to obtain a processor allocation. In some embodiments, the interconnected processors are conceptualized as a generally rectangular 3-dimensional grid, and the MC allocation algorithm is applied with respect to the 3-dimensional grid.